package com.zp.self.module.level_4_算法练习.数据结构.设计结构;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author By ZengPeng
 */
public class 力扣_146_LRU缓存 {
    @Test
    public void main() {

        LRUCache lRUCache = new LRUCache(3);
        lRUCache.put(1, 1); // 缓存是 {1=1}
        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
        lRUCache.put(3, 3); // 缓存是 {1=1, 2=2}
        lRUCache.put(4, 4); // 缓存是 {1=1, 2=2}
        System.out.println(lRUCache.get(4));  // 返回 1
        System.out.println(lRUCache.get(3));  // 返回 1
        System.out.println(lRUCache.get(2));  // 返回 1
        System.out.println(lRUCache.get(1));  // 返回 1
        lRUCache.put(5, 5); // 缓存是 {1=1, 2=2}
        System.out.println(lRUCache.get(2)); // 返回 2 (未找到)
    }

    /**
    题目：请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
     实现 LRUCache 类：
     LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
     int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
     void put(int key, int value) 
         如果关键字 key 已经存在，则变更其数据值 value ；
         如果不存在，则向缓存中插入该组 key-value 。
         如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
     函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

     示例：
     输入
     ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
     [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
     输出
     [null, null, null, 1, null, -1, null, -1, 3, 4]
     解释
     LRUCache lRUCache = new LRUCache(2);
     lRUCache.put(1, 1); // 缓存是 {1=1}
     lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
     lRUCache.get(1);    // 返回 1
     lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
     lRUCache.get(2);    // 返回 -1 (未找到)
     lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
     lRUCache.get(1);    // 返回 -1 (未找到)
     lRUCache.get(3);    // 返回 3
     lRUCache.get(4);    // 返回 4

    分析：【B 💔💔💔💔】
       1.用双向链表+Map：Node记录前后节点,Map记录每个节点是否存在
                --执行用时：42 ms, 在所有 Java 提交中击败了76.05%的用户
                --时长：超过2小时

    边界值 & 注意点：
       1.
     **/
    class LRUCache {
        Map<Integer,Node> map ;
        Node first =new Node();
        Node end=new Node();
        int size;
        public LRUCache(int capacity) {
            map= new HashMap<>(capacity);
            size=capacity;
            end.pro=first;
            first.next=end;
        }

        public int get(int key) {
            if(map.containsKey(key)){
                Node node = map.get(key);
                node.pro.next=node.next;
                node.next.pro=node.pro;

                node.pro=end.pro;
                node.next=end;

                end.pro.next=node;
                end.pro=node;

                return  end.pro.value;
            }else {
                return -1;
            }
        }

        public void put(int key, int value) {
            if(map.containsKey(key)){
                Node node = map.get(key);
                node.pro.next=node.next;
                node.next.pro=node.pro;

                node.pro=end.pro;
                node.next=end;
                node.value=value;

                end.pro.next=node;
                end.pro=node;
            }else {
                Node node = new Node(end.pro, end, key, value);

                node.pro.next=node;
                end.pro=node;

                map.put(key,node);
            }
            if(map.size()>size){
                Node next = first.next;
                next.pro.next = next.next;
                next.next.pro=next.pro;
                map.remove(next.key) ;
            }
        }
    }

    class Node{
         Node pro;
         Node next;
         int key;
         int value;
        public Node(){

        }
        public Node( Node pro, Node next,int key,int value){
            this.pro=pro;
            this.next=next;
            this.key=key;
            this.value=value;
        }
    }
}
